package algorithm.sort;

/**
 * @Author liuhaoqi
 * @Date 2020/12/19 16:17
 * @Version 1.0
 * 希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {1, 2, 6, 7, 8, 9, 9, 1, 7};
        int[] arrs = shellSort(arr);
        for (int i : arrs) {
            System.out.println(i);
        }
    }

    public static int[] shellSort(int[] array) {
        int n = array.length;
        //增量gap 为 数组长度一半
        int temp, gap = n / 2;
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    //插入排序 如果比较的数组中的元素比当前元素大，就把比较的数组的元素后移
                    array[preIndex + gap] = array[preIndex];
                    //并且比较索引继续前移
                    preIndex -= gap;
                }
                //比较的数组元素比当前元素要小。则把当前元素放在比较的元素后面
                array[preIndex + gap] = temp;
            }
            gap = gap / 2;
        }
        return array;
    }
}
